#include <vector>

using namespace std;

/* 快速排序（尾递归优化） */
void quickSort(vector<int>& nums, int left, int right) {
    while (left < right) {
        int pivot = partition(nums, left, right);
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1);
            left = pivot + 1;
        } else {
            quickSort(nums, pivot + 1, right);
            right = pivot - 1;
        }
    }
}

/* 哨兵划分（三数取中值） */
int partition(vector<int>& nums, int left, int right) {
    int med = medianThree(nums, left, (left + right) / 2, right);
    swap(nums[left], nums[med]);
    int base = nums[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= base)
            j--;
        while (i < j && nums[i] <= base)
            i++;
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[left]);
    return i;
}

/* 选取三个元素的中位数 */
int medianThree(vector<int>& nums, int left, int mid, int right) {
    if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
        return left;
    else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
        return mid;
    else
        return right;
}
